/*
 * @lc app=leetcode.cn id=1438 lang=typescript
 *
 * [1438] 绝对差不超过限制的最长连续子数组
 */

// @lc code=start
function longestSubarray(nums: number[], limit: number): number {
  // 检测长度为l字符串是否满足题意
  const m = nums.length;
  // 判定函数，维护窗口区间的最大值和最小值，然后判断差集是否大于等于limit
  const isCheck = (l: number): boolean => {
    // 单调递增
    const dequeAsc: number[] = [];
    // 单调递减
    const dequeDsc: number[] = [];
    for (let i = 0; i < m; i++) {
      while (dequeAsc.length && nums[i] < nums[dequeAsc[dequeAsc.length - 1]]) {
        dequeAsc.pop();
      }
      while (dequeDsc.length && nums[i] > nums[dequeDsc[dequeDsc.length - 1]]) {
        dequeDsc.pop();
      }
      dequeAsc.push(i);
      dequeDsc.push(i);
      if (i + 1 < l) continue;
      if (i - dequeAsc[0] === l) dequeAsc.shift();
      if (i - dequeDsc[0] === l) dequeDsc.shift();

      if (nums[dequeDsc[0]] - nums[dequeAsc[0]] <= limit) return true;
    }
    return false;
  };

  // 再长度[0,m]之间找最大符合题意的长度
  let l = 0;
  let r = m;
  while (l < r) {
    // 往后找，这里需要加1
    let mid = (r + l + 1) >> 1;

    if (isCheck(mid)) l = mid;
    else r = mid - 1;
  }

  return l;
}
// @lc code=end
